package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC362 {

    static class Solution {
        /**
         * @param nums: A list of integers.
         * @param k:    An integer
         * @return: The maximum number inside the window at each moving.
         */
        public List<Integer> maxSlidingWindow(int[] nums, int k) {
            //滑动窗口
            List<Integer> ans = new ArrayList<>();
            LinkedList<Integer> ll = new LinkedList<>();
            for (int i = 0; i <nums.length; i++) {
                while (!ll.isEmpty() && nums[ll.peekLast()] < nums[i]){
                    ll.pollLast();
                }

                ll.add(i);

                if(ll.peekFirst() == i-k){
                    ll.pollFirst();
                }

                if(ll.peekLast()>=k-1){
                    ans.add(nums[ll.peekFirst()]);
                }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.maxSlidingWindow(new int[]{1,2,7,7,8},3));
        System.out.println(obj.maxSlidingWindow(new int[]{1,2,7,7,2},3));
    }
}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有198条未读消息，请及时查看
362 · 滑动窗口的最大值
算法
困难
通过率
36%

题目
题解50
笔记
讨论99+
排名
记录
描述
给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入:
[1,2,7,7,8]
3
输出:
[7,7,8]

解释：
最开始，窗口的状态如下：`[|1, 2 ,7| ,7 , 8]`, 最大值为 `7`;
然后窗口向右移动一位：`[1, |2, 7, 7|, 8]`, 最大值为 `7`;
最后窗口再向右移动一位：`[1, 2, |7, 7, 8|]`, 最大值为 `8`.
样例 2:

输入:
[1,2,3,1,2,3]
5
输出:
[3,3]

解释:
最开始，窗口的状态如下： `[|1,2,3,1,2 | ,3]` , 最大值为`3`;
然后窗口向右移动一位.`[1, |2,3,1,2,3]`, 最大值为 `3`;
挑战
O(n)时间，O(k)的额外空间

相关知识
学习《2024年6月北美大厂最新面试真题精讲》课程中的3.1Bytedance：最新面试精选001相关内容 ，了解更多相关知识！
标签
企业
Amazon
Zenefits
Microsoft
Google
相关题目

558
滑动窗口矩阵的最大值
中等

604
滑动窗口内数的和
简单

692
滑动窗口内唯一元素数量和
中等

360
滑动窗口的中位数
困难

516
房屋染色 II
困难

928
最多有两个不同字符的最长子串
中等
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
343/1857
已开启智能提示
发起考试
45 分 00 秒
123456789101112131415161718192021222324252627
public class Solution {
    /**
     * @param nums: A list of integers.
     * @param k: An integer
     * @return: The maximum number inside the window at each moving.

 */